iT邦幫忙

2024 iThome 鐵人賽

DAY 10
0
Software Development

離塵指引.卷之一.試結丹:程式語言自舉系列 第 10

零.一版分詞器(二)算法及其狀態機表示

  • 分享至 

  • xImage
  •  

上一節中變數的詞法定義並不清楚,例如,變數不可以是「元」,但能不能是「元氣」呢?變數能不能包含數字,像是「2號機」?若允許這樣的寬鬆定義,分詞會較為困難,當讀取到「元」時,並無法確定現在正在讀取「元」關鍵字,同時也可能只讀到「元氣」變數的開頭而已。同理,當讀到[0-9]時,無法判定正在讀取數字,還是某個變數的開頭。

但無妨,早已有成熟的演算法能應對這類複雜狀況,在零・一版的簡單狀況,倒也不必構思出通用算法才能分詞,只要仔細分析所有狀況就可以了。

為了方便後續表達,先令 x 代表除了零字詞以及[0-9]的所有字元集合。

當目前讀取到的字串是...

  • 除了元之外的單字詞,亦即()+−*/=・
    • 讀取到一個字即可確定為詞
    • 可能是變數的前綴,當下一個字元屬於 x 或 [0-9] ,即確定該詞為變數
    • 當下個字元不是上述狀況時,是元關鍵字
  • [0-9]+
    • 可能是變數的前綴,當下一個字元屬於 x ,即確定該詞為變數
    • 當下個字元不是上述狀況時,是數字
  • x
    • 必是變數

下圖把上述分析畫成了狀態機,但該圖並沒有畫出所有單字詞,僅以加減為例,其餘單字詞請道友自行想像。

零・一版分詞狀態機

分詞器會不斷接收到字元,分詞器根據接收的字元維護自身狀態。初始狀態是「起點」,每接收到一個字元,就嘗試匹配實線,若無法匹配,就精油虛線回到原點,並且根據當下狀態分詞。

畫出狀態機之後,以法咒(程式語言)依樣畫葫蘆實作,就是件很容易的事了。


上一篇
零.一版分詞器(一)定義
下一篇
零.一版分詞器(三)實作
系列文
離塵指引.卷之一.試結丹:程式語言自舉13
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言